package com.algorithms.techniques.graph;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import com.algorithms.absdatatypes.MinPriorityQueue;
import com.algorithms.absdatatypes.Node;
import com.algorithms.datatypes.GraphNodeImpl;
import com.algorithms.datatypes.MinPriorityQueueImpl;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.Graph;

public class PrimsSpanningTree<V, E extends Comparable> implements
		SpanningTree<V, E>
{
	//Define a maximum and minimum value
	E infinity;
	E minimum;
	//keep track of the nodes in priority queue so that it can be reference in O(1) time
	Map<V, Node<E, V>> pointToNodeInPQ;
	//As we build the spanning tree the parent of vertex is updated 
	Map<V, Node<E, V>> parentOfVertex;

	public void setInfinity(E iInfinity)
	{
		infinity = iInfinity;
	}

	public void setMinimum(E iMinimum)
	{
		minimum = iMinimum;
	}

	public PrimsSpanningTree(E infinity, E minimum)
	{
		this.infinity = infinity;
		this.minimum = minimum;
	}

	
	public Graph<V, E> createSpanningTree(Graph<V, E> graph)
	{
		Graph<V, E> spanningTree = null;
		try
		{
			spanningTree = new DirectedSparseMultigraph<V, E>();
			pointToNodeInPQ = new HashMap<V, Node<E, V>>();
			parentOfVertex = new HashMap<V, Node<E, V>>();
			MinPriorityQueue<E, V> priorityQueue = new MinPriorityQueueImpl<E, V>();
			// Iterate through all the vertices and insert in spanning tree
			Collection<V> vertices = graph.getVertices();
			Node<E, V> node = null;
			int count = 0;
			//Initialize the maps and insert into priority queue
			for (V vertex : vertices)
			{
				node = new GraphNodeImpl<E, V>(infinity, vertex);
				pointToNodeInPQ.put(vertex, node);
				parentOfVertex.put(vertex, null);
				priorityQueue.insert(node);
			}
			//Reduce one of the nodes and reorder the priority queue
			Node<E, V> nodeNew = new GraphNodeImpl<E, V>(minimum,
					node.getData());
			priorityQueue.decreaseKey(node, nodeNew);
			while (!priorityQueue.isEmpty())
			{
				//Extract the priority queue's minimum value
				Node<E, V> nodeMin = priorityQueue.extractMin();
				pointToNodeInPQ.remove(nodeMin.getData());
				
				// Iterate through the neighbours of extracted node and upate the
				// minimum distances of the nodes in priority queue. Also update the 
				// parents of the neighbours residing in priority queue
				for (V neighbour : graph.getNeighbors(nodeMin.getData()))
				{
					if (pointToNodeInPQ.containsKey(neighbour))
					{

						E edge = graph.findEdge(nodeMin.getData(), neighbour);
						if (edge != null)
						{ // edge = graph.findEdge(neighbour,nodeMin.getData());
							Node<E, V> edgeNodeInPriorityQueue = pointToNodeInPQ
									.get(neighbour);
							//Check if there is a smaller edge with respect to extracted 
							//node with the priority queue nodes
							if (edgeNodeInPriorityQueue != null
									&& edge.compareTo(edgeNodeInPriorityQueue
											.getKey()) < 0)
							{
								Node<E, V> nodeNewPQ = new GraphNodeImpl<E, V>(
										edge, edgeNodeInPriorityQueue.getData());
								pointToNodeInPQ.put(neighbour, nodeNewPQ);
								//If there is a smaller edge then reorder the node in the queue
								priorityQueue.decreaseKey(
										edgeNodeInPriorityQueue, nodeNewPQ);
								//Update the parent of the updated node in queue
								Node<E, V> nodeData = new GraphNodeImpl<E, V>(
										edge, nodeMin.getData());
								parentOfVertex.put(neighbour, nodeData);

							}
						}
					}
				}
			}
			//Create a spanning tree with the  parent of all the vertices
			for (Entry<V, Node<E, V>> entry : parentOfVertex.entrySet())
			{
				V vertex = entry.getKey();
				Node<E, V> nodeVal = entry.getValue();
				if (nodeVal != null)
					spanningTree.addEdge(nodeVal.getKey(), nodeVal.getData(),
							vertex);
			}
		} catch (Exception e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return spanningTree;
	}

}
